package com.gitee.wsl.struct.tree.sample.color


import com.gitee.wsl.base.Option
import com.gitee.wsl.base.Tuple2
import com.gitee.wsl.base.none
import com.gitee.wsl.base.some
import com.gitee.wsl.collections.iterator.EmptyIterator
import com.gitee.wsl.ext.list.pop
import com.gitee.wsl.ext.list.push
import com.gitee.wsl.struct.tree.sample.color.RedBlackTree.Color.BLACK
import com.gitee.wsl.struct.tree.sample.color.RedBlackTreeModule.Empty
import com.gitee.wsl.struct.tree.sample.color.RedBlackTreeModule.Node

/**
 * Purely functional Red/Black Tree, inspired by [Kazu Yamamoto's Haskell implementation](https://github.com/kazu-yamamoto/llrbtree/blob/master/Data/Set/RBTree.hs).
 *
 *
 * Based on
 *
 *  * [Chris Okasaki, "Red-Black Trees in a Functional Setting", Journal of Functional Programming, 9(4), pp 471-477, July 1999](http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#jfp99)
 *  * Stefan Kahrs, "Red-black trees with types", Journal of functional programming, 11(04), pp 425-432, July 2001
 *
 *
 * @param <T> Component type
 * @author Daniel Dietrich
</T> */
interface RedBlackTree<T> : Iterable<T> {
    /**
     * Inserts a new value into this tree.
     *
     * @param value A value.
     * @return A new tree if this tree does not contain the given value, otherwise the same tree instance.
     */
    fun insert(value: T): RedBlackTree<T> {
        return Node.insert(this, value).color(BLACK)
    }

    /**
     * Return the [Color] of this Red/Black Tree node.
     *
     *
     * An empty node is `BLACK` by definition.
     *
     * @return Either `RED` or `BLACK`.
     */
    fun color(): Color

    /**
     * Returns the underlying [java.util.Comparator] of this RedBlackTree.
     *
     * @return The comparator.
     */
    fun comparator(): Comparator<T>?

    /**
     * Checks, if this `RedBlackTree` contains the given `value`.
     *
     * @param value A value.
     * @return true, if this tree contains the value, false otherwise.
     */
    fun contains(value: T): Boolean

    /**
     * Deletes a value from this RedBlackTree.
     *
     * @param value A value
     * @return A new RedBlackTree if the value is present, otherwise this.
     */
    fun delete(value: T): RedBlackTree<T> {
        val tree: RedBlackTree<T> = Node.delete(this, value).first
        return Node.color(tree, BLACK)
    }

    fun difference(tree: RedBlackTree<T>): RedBlackTree<T> {
        if (isEmpty || tree.isEmpty) {
            return this
        } else {
            val that: Node<T> = tree as Node<T>
            val split: Tuple2<RedBlackTree<T>, RedBlackTree<T>> = Node.split(this, that.value)
            return Node.merge(split.first.difference(that.left), split.second.difference(that.right))
        }
    }

    /**
     * Returns the empty instance of this RedBlackTree.
     *
     * @return An empty ReadBlackTree
     */
    fun emptyInstance(): RedBlackTree<T>

    /**
     * Finds the value stored in this tree, if exists, by applying the underlying comparator to the tree elements and
     * the given element.
     *
     *
     * Especially the value returned may differ from the given value, even if the underlying comparator states that
     * both are equal.
     *
     * @param value A value
     * @return Some value, if this tree contains a value equal to the given value according to the underlying comparator. Otherwise None.
     */
    fun find(value: T): Option<T>

    fun intersection(tree: RedBlackTree<T>): RedBlackTree<T> {
        if (isEmpty) {
            return this
        } else if (tree.isEmpty) {
            return tree
        } else {
            val that: Node<T> = tree as Node<T>
            val split: Tuple2<RedBlackTree<T>, RedBlackTree<T>> = Node.split(this, that.value)
            return if (contains(that.value)) {
                Node.join(
                    split.first.intersection(that.left),
                    that.value,
                    split.second.intersection(that.right)
                )
            } else {
                Node.merge(split.first.intersection(that.left), split.second.intersection(that.right))
            }
        }
    }

    /**
     * Checks if this `RedBlackTree` is empty, i.e. an instance of `Leaf`.
     *
     * @return true, if it is empty, false otherwise.
     */
    val isEmpty: Boolean

    /**
     * Returns the left child if this is a non-empty node, otherwise throws.
     *
     * @return The left child.
     * @throws UnsupportedOperationException if this RedBlackTree is empty
     */
    fun left(): RedBlackTree<T>?

    /**
     * Returns the maximum element of this tree according to the underlying comparator.
     *
     * @return Some element, if this is not empty, otherwise None
     */
    fun max(): Option<T> {
        return if (isEmpty) Option.none() else Option.some(Node.maximum(this as Node<T>))
    }

    /**
     * Returns the minimum element of this tree according to the underlying comparator.
     *
     * @return Some element, if this is not empty, otherwise None
     */
    fun min(): Option<T> {
        return if (isEmpty) Option.none() else Option.some(Node.minimum(this as Node<T>))
    }

    /**
     * Returns the right child if this is a non-empty node, otherwise throws.
     *
     * @return The right child.
     * @throws UnsupportedOperationException if this RedBlackTree is empty
     */
    fun right(): RedBlackTree<T>?

    /**
     * Returns the size of this tree.
     *
     * @return the number of nodes of this tree and 0 if this is the empty tree
     */
    fun size(): Int

    /**
     * Adds all of the elements of the given `tree` to this tree, if not already present.
     *
     * @param tree The RedBlackTree to form the union with.
     * @return A new RedBlackTree that contains all distinct elements of this and the given `tree`.
     */
    fun union(tree: RedBlackTree<T>): RedBlackTree<T> {
        if (tree.isEmpty) {
            return this
        } else {
            val that: Node<T> = tree as Node<T>
            if (isEmpty) {
                return that.color(BLACK)
            } else {
                val split: Tuple2<RedBlackTree<T>, RedBlackTree<T>> = Node.split(this, that.value)
                return Node.join(split.first.union(that.left), that.value, split.second.union(that.right))
            }
        }
    }

    /**
     * Returns the value of the current tree node or throws if this is empty.
     *
     * @return The value.
     * @throws NoSuchElementException if this is the empty node.
     */
    fun value(): T

    /**
     * Returns an Iterator that iterates elements in the order induced by the underlying Comparator.
     *
     *
     * Internally an in-order traversal of the RedBlackTree is performed.
     *
     *
     * Example:
     *
     * <pre>`
     * 4
     * / \
     * 2   6
     * / \ / \
     * 1 3 5 7
    `</pre> *
     *
     * Iteration order: 1, 2, 3, 4, 5, 6, 7
     *
     *
     * See also [Implement Iterator for BinaryTree I (In-order)](http://n00tc0d3r.blogspot.de/2013/08/implement-iterator-for-binarytree-i-in.html).
     */
    override fun iterator(): Iterator<T> {
        if (isEmpty) {
            return EmptyIterator
        } else {
            val that: Node<T> = this as Node<T>
            return object : Iterator<T> {
                var stack = pushLeftChildren(ArrayList(), that)

                override fun hasNext(): Boolean {
                    return stack.isNotEmpty()
                }

                override fun next(): T {
                    val result = stack.pop() as Tuple2<Node<T>, MutableList<Node<T>>>
                    val node: Node<T> = result.first
                    stack = if (node.right.isEmpty)
                        result.second
                    else
                        pushLeftChildren(result.second, node.right as Node<T>
                        )
                    return result.first.value
                }

//                val next: T
//                    get() {
//                        val result = stack.pop() as Tuple2<Node<T>, out MutableList<Node<T>>>
//                        val node: Node<T> = result.first
//                        stack = if (node.right.isEmpty)
//                                    result.second
//                               else
//                                   pushLeftChildren(result.second, node.right as Node<T>
//                        )
//                        return result.first.value
//                    }

                fun pushLeftChildren(initialStack: MutableList<Node<T>>, that: Node<T>): MutableList<Node<T>> {
                    var stack: MutableList<Node<T>> = initialStack
                    var tree: RedBlackTree<T> = that
                    while (!tree.isEmpty) {
                        val node: Node<T> = tree as Node<T>
                        stack.push(node)
                        tree = node.left
                    }
                    return stack
                }
            }
        }
    }

    /**
     * Returns a Lisp like representation of this tree.
     *
     * @return This Tree as Lisp like String.
     */
    override fun toString(): String

    enum class Color {
        RED, BLACK;

        override fun toString(): String {
            return if ((this == RED)) "R" else "B"
        }
    }

    companion object {
        fun <T> empty(comparator: Comparator<T>): RedBlackTree<T> {
            return Empty(comparator)
        }

        fun <T> of(comparator: Comparator<T>, value: T): RedBlackTree<T> {
            val empty: Empty<T> = Empty(comparator)
            return Node(BLACK, 1, empty, value, empty, empty)
        }


        fun <T> of(comparator: Comparator<T>, vararg values: T): RedBlackTree<T> {
            var tree = empty<T>(comparator)
            for (value in values) {
                tree = tree.insert(value)
            }
            return tree
        }

        fun <T> ofAll(
            comparator: Comparator<T>,
            values: Iterable<T>,
        ): RedBlackTree<T> {
            // function equality is not computable => same object check
            if (values is RedBlackTree<*> && (values as RedBlackTree<T>).comparator() === comparator) {
                return values as RedBlackTree<T>
            } else {
                var tree = empty<T>(comparator)
                for (value in values) {
                    tree = tree.insert(value)
                }
                return tree
            }
        }

    }
}

